package primary.primary0;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 这里的去重很重要, 核心是保证只会从小到大枚举
 */
public class S0039组合总和 {
    /**
     * 52, 回溯, 纯指数复杂度, 去重?
     * 层序遍历, 和答案方式一样
     * 背包问题, 直接枚举, 是指数时间复杂度, 会超时;
     * 完全背包问题(好像不是), 物品可以无限使用;
     * 全排列, 回溯, 不会超时吗?
     */
    private int totalLen = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        totalLen = candidates.length;
        List<List<Integer>> resList = new LinkedList<>();
        // int[] curCandiNums = new int[candidates.length];
        List<Integer> curCandiNums = new LinkedList<>();
        helpCombination(candidates, target, curCandiNums, resList, 0);

        return resList;

    }
    // 为了去重使用一个标志位startLoc, 好用
    // 穷举的时候, 对2, 3, 4这种, 只会从小往大举, 不会出现2, 3 和3, 2同时出现的情况
    public void helpCombination(int[] candidates, int target, List<Integer> curCandiNums, List<List<Integer>> resList, int startLoc){
        if(target > 0){
            for(int i = startLoc; i < totalLen; i++){
                // mark:注意这里一加一减的回溯，一个一个扣和每次遍历只扣startLoc位置的，每次扣target/candidate[startloc]这么多次，是一样的，就是要注意有put有remove
                curCandiNums.add(candidates[i]);
                helpCombination(candidates, target - candidates[i], curCandiNums, resList, i);
                // curCandiNums.remove((Integer)candidates[i]);, 不知道为啥这两句时间没区别, 应该差很多才对
                curCandiNums.remove(curCandiNums.size() - 1); // 这个操作没问题
            }
        }else if(target == 0){
            // 保留当前情况
            // resList.add(curCandiNums.stream().collect(Collectors.toList())); 性能很差
            resList.add(new ArrayList<>(curCandiNums)); // 可以这样拷贝, 性能高
        }
        // 扣多了导致target<0这种case，直接被不处理忽略了
    }
}
